package com.qh.test;

import com.qh.printer.BinaryTreeInfo;

/**
 * @description:
 * @author: zqh
 * @date: 2021/11/15 10:40
 **/
public class BST<E> implements BinaryTreeInfo {
    private int size;
    private Node<E> root;



    private static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;

        public Node(E element) {
            this.element = element;
        }
    }

    public int size(){
        return size;
    }

    public void add(E element){

        //添加第一个节点
        if (root == null){
            root = new Node<>(element);
            size++;
            return;
        }

        //添加的不是第一个节点
        //找到父节点
        Node<E> patent = root;
        Node<E> node = root;
        int cmp = 0;
        do {
            cmp = compare(element, node.element);
            patent = node;
            if (cmp > 0){
                node = node.right;
            } else if (cmp < 0){
                node = node.left;
            } else {
                node.element = element;
                return;
            }
        } while (node != null);

        //看看插入到父节点的那个位置
        Node<E> newNode = new Node<>(element);
        if (cmp > 0){
            patent.right = newNode;
        } else {
            patent.left = newNode;
        }
        size++;
    }

    public void remove(E element){

    }

    /**
     * 前序遍历
     */
    public void qxbl(){
        qxbl(root);
    }

    private void qxbl(Node<E> node){
        if (node == null) {
            return;
        }
        System.out.println(node.element);
        qxbl(node.left);
        qxbl(node.right);
    }

    /**
     * 中序遍历
     */
    public void zxbl(){
        zxbl(root);
    }

    private void zxbl(Node<E> node){
        if (node == null) {
            return;
        }
        zxbl(node.left);
        System.out.println(node.element);
        zxbl(node.right);
    }

    /**
     * 后序遍历
     */
    public void hxbl(){
        hxbl(root);
    }

    private void hxbl(Node<E> node){
        if (node == null) {
            return;
        }
        hxbl(node.left);
        hxbl(node.right);
        System.out.println(node.element);
    }


    private Node<E> node(E element){
        Node<E> node = root;
        while (node != null){
            int cmp = compare(element,node.element);
            if (cmp == 0) {
                return node;
            }
            if (cmp > 0){
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    /**
     *  @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
     */
    private int compare(E e1, E e2){
        return  ((Comparable<E>)e1).compareTo(e2);
    }


    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
        String parentString = "null";
        return myNode.element + "_p(" + parentString + ")";
    }
}
